#include<iostream>
#include<assert.h>
#include<stack>

using std::cin;
using std::cout;
using std::endl;
using std::stack;
using std::swap;


template<typename T>
int _sort(T* s, int begin, int end)
{
  int left = begin;
  int right = begin + 1;

  while(right <= end)
  {
    if (s[right] < s[begin] && ++left != right)
      swap(s[right], s[left]);
    right++;
  }
  swap(s[left], s[begin]);
  return left;
}

template<typename T>
int find(T* s,int length, const T& val)
{
  assert(s);

  // 快速排序的非递归双指针版本(没有进行优化)
  stack<int> t;
  t.push(length - 1);
  t.push(0);
  while(!t.empty())
  {
    int begin = t.top();
    t.pop();
    int end = t.top();
    t.pop();

    int keyi = _sort(s, begin, end);
    if (keyi + 1 < end)
    {
      t.push(end);
      t.push(keyi + 1);
    }
    if (keyi - 1 > begin)
    {
      t.push(keyi - 1);
      t.push(begin);
    }
  }

  // 二分法开始寻找
  int begin = 0;
  int end = length - 1;
  while (begin <= end)
  {
    int m = (end - begin) / 2 + begin;
    if (s[m] == val)
      return m;
    if (s[m] < val)
      begin = m + 1;
    else 
      end = m - 1;
  }
  // 出来了说明没有找到
  return -1;
}
